#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <queue>

using namespace std;

struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode() : val(0), left(nullptr), right(nullptr) {}
     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Solution {
public:
    bool isEvenOddTree(TreeNode* root)
    {
        queue<TreeNode*> qu;
        qu.push(root);
        int level = 0;
        while (!qu.empty())
        {
            int size = qu.size();
            int prev = level % 2 == 0 ? INT_MIN : INT_MAX;
            while (size--)
            {
                TreeNode* temp = qu.front();
                qu.pop();
                if (level % 2 == temp->val % 2)
                {
                    return false;
                }
                if (level % 2 == 0 && temp->val <= prev || level % 2 != 0 && temp->val >= prev)
                {
                    return false;
                }
                if (temp->left != nullptr)
                {
                    qu.push(temp->left);
                }

                if (temp->right != nullptr)
                {
                    qu.push(temp->right);
                }
                prev = temp->val;
            }
            level++;
        }
        return true;
    }
};

int main()
{
	return 0;
}